//
// Created by liushuai on 2020/5/17.
//
#include "restoreIpAddresses.h"
<<<<<<< HEAD:cxx/algorithm/src/restoreIpAddresses.cc
void dfs(std::string& s,std::vector<std::string>& result,std::vector<std::string>& maybe,int start){
    if(start==s.size()&&maybe.size() == 4){//字符串被分成四段同时遍历完整个字符
        std::string ip_string = maybe[0];
        for(int index = 1;index<4;index++)
            ip_string += "."+maybe[index];
        result.push_back(ip_string);
        return;
    }
    else if(start<s.size() && maybe.size() == 4){//找到四段，但是没有到字符串末尾
        return;
    }
    else{
        for(int length=1;length<4;length++){
            if (length != 1 && s[start] == '0') //当前可选的字符长度为2,3但是第一个元素是0的是不合法情况例如 01,但是0是合法的
                return;
            else if(start>=s.size())//递归遍历结束了
                return;
            else{
                // 还在遍历，判断字符串是否合适
                int num_elem = std::atoi(s.substr(start,length).c_str());

                if(num_elem>=0 && num_elem<=255){
                    maybe.push_back(s.substr(start,length));
                    dfs(s,result,maybe,start+length);
                    maybe.pop_back();
                } else
                    return;

            }
        }
    }
}
std::vector<std::string> restoreIpAddresses(std::string s) {
    std::vector<std::string> result;
    std::vector<std::string> maybe;
    dfs(s,result,maybe,0);
    return result;

=======
void dfs(std::string& s, std::vector<std::string>& result,
         std::vector<std::string>& maybe, int start) {
  if (start == s.size() &&
      maybe.size() == 4) {  // 字符串被分成四段同时遍历完整个字符
    std::string ip_string = maybe[0];
    for (int index = 1; index < 4; index++) ip_string += "." + maybe[index];
    result.push_back(ip_string);
    return;
  } else if (start < s.size() &&
             maybe.size() == 4) {  // 找到四段，但是没有到字符串末尾
    return;
  } else {
    for (int length = 1; length < 4; length++) {
      if (length != 1 && s[start] == '0')  // 当前可选的字符长度为2,3但是第一个元素是0的是不合法情况例如
                                           // 01,但是0是合法的
        return;
      else if (start >= s.size())  // 递归遍历结束了
        return;
      else {
        // 还在遍历，判断字符串是否合适
        int num_elem = std::atoi(s.substr(start, length).c_str());

        if (num_elem >= 0 && num_elem <= 255) {
          maybe.push_back(s.substr(start, length));
          dfs(s, result, maybe, start + length);
          maybe.pop_back();
        } else
          return;
      }
    }
  }
}
std::vector<std::string> restoreIpAddresses(std::string s) {
  std::vector<std::string> result;
  std::vector<std::string> maybe;
  dfs(s, result, maybe, 0);
  return result;
>>>>>>> dev:cxx/algorithm/common/src/restoreIpAddresses.cc
}